package cn.fansunion.leecode.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 多数元素(有很多种解法)
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author wen.lei@brgroup.com
 *
 * 2022-1-24
 */
public class MajorityElement {
    
    /**
     * 数字转map，num->count；比较所有num的count大小，找到最大的count，返回丢应的num
     * LeetCode不能识别Entry,Map.Entry能识别
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        //数字转map，num->count
        Map<Integer,Integer> numCountMap=new HashMap<>();
        for (int num : nums) {
           Integer count= numCountMap.get(num);
           if(count==null) {
               count=1;
           }else {
               count++;
           }
           numCountMap.put(num, count);
        }
        //比较所有num的count大小，找到最大的count，返回丢应的num
        Integer maxNum=null;
        Integer maxCount = null;
        for (Map.Entry<Integer, Integer> entry : numCountMap.entrySet()) {
            if(maxNum==null) {
                maxNum=entry.getKey();
                maxCount= entry.getValue();
            }else {
                if(entry.getValue() > maxCount) {
                    maxNum=entry.getKey();
                    maxCount=entry.getValue();
                }
            }
           
        }
        return maxNum;
    }
}
